// 01背包(模版)
// 给定一个正数t，表示背包的容量
// 有m个货物，每个货物可以选择一次
// 每个货物有自己的体积costs[i]和价值values[i]
// 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
// 返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1048
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率较高的写法
// 提交以下的所有代码，可以直接通过

#include <bits/stdc++.h>

using namespace std;

const int MAXM = 101;
const int MAXT = 1001;
int cost[MAXM];
int val[MAXM];
int dp[MAXT];
int t, m;

int read()
{
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = 10 * x + ch - '0';
        ch = getchar();
    }
    return f * x;
}

// 严格位置依赖的动态规划
// n个物品编号1~n，第i号物品的花费cost[i]、价值val[i]
// cost、val数组是全局变量，已经把数据读入了
int compute1()
{
    int dp[m + 1][t + 1];
    memset(dp, 0, sizeof dp);
    for(int i = 1; i <= m; ++i)
    {
        for(int j = 0; j <= t; ++j)
        {
            // 不要i号物品
            dp[i][j] = dp[i - 1][j];
            // 要i号物品
            if(j >= cost[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - cost[i]] + val[i]);
        }
    }
    return dp[m][t];
}

// 空间压缩
int compute2()
{
    fill(dp + 1, dp + t + 1, 0);
    for(int i = 1; i <= m; ++i)
    {
        for(int j = t; j >= cost[i]; --j)
        {
            dp[j] = max(dp[j], dp[j - cost[i]] + val[i]);
        }
    }
    return dp[t];
}

int main()
{
    t = read(), m = read();
    for(int i = 1; i <= m; ++i) 
    {
        cost[i] = read();
        val[i] = read();
    }
    printf("%d\n", compute2());

    return 0;
}